import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc]==color) return image;

        dfs(sr,sc,image,color);

        return image;


    }

    private void dfs(int sr,int sc,int[][] image,int color){
        int m=image.length;
        int n=image[0].length;
        int or=image[sr][sc];
        image[sr][sc]=color;
        for(int i=0;i<4;i++){
            int x=dx[i]+sr;
            int y=dy[i]+sc;

            if(x>=0&&x<m&&y>=0&&y<n&&or==image[x][y]) dfs(x,y,image,color);
        }



    }
}





//超绝正难则反
class Solution2 {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> ret = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return ret;
        }

        int m = heights.length;
        int n = heights[0].length;

        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        // DFS from Pacific borders (first row and first column)
        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, i, 0);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, 0, j);
        }

        // DFS from Atlantic borders (last row and last column)
        for (int i = 0; i < m; i++) {
            dfs(heights, atlantic, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, atlantic, m - 1, j);
        }

        // Collect results
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    ret.add(Arrays.asList(i, j));
                }
            }
        }

        return ret;
    }

    private void dfs(int[][] heights, boolean[][] visited, int x, int y) {
        int m = heights.length;
        int n = heights[0].length;

        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && heights[nx][ny] >= heights[x][y]) {
                dfs(heights, visited, nx, ny);
            }
        }
    }
}


//记忆化搜索
class Solution4 {
    public int getMoneyAmount(int n) {
        int[][] memo=new int[n+1][n+1];
        return dfs(1,n,memo);
    }

    public int dfs(int i,int j,int[][] memo){
        if(i>=j) return 0;
        if(memo[i][j]!=0) return memo[i][j];

        int ret=0x3f3f3f3f;

        for(int k=i;k<=j;k++){


            int l=dfs(i,k-1,memo);
            int r=dfs(k+1,j,memo);

            ret=Math.min(Math.max(l,r)+k,ret);

        }

        memo[i][j]=ret;
        return ret;
    }
}